/****************************************************************

kernel/malloc.c
malloc() and family for AWOS

Copyright (c) 2006 Andrew Wilcox. All rights reserved.

Redistribution and use in source and binary forms, with or
without modification, are permitted provided that the following
conditions are met:

1. Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above
copyright notice, this list of conditions and the following
disclaimer in the documentation and/or other materials provided
with the distribution.

3. The end-user documentation included with the redistribution,
if any, must include the following acknowledgment:

"This product includes software developed by Andrew Wilcox for
AWOS. (http://code.google.com/p/awos)."

Alternately, this acknowledgment may appear in the software
itself, if and wherever such third-party acknowledgments normally
appear.

4. The names "AWOS" and "Andrew Wilcox" must not be used to
endorse or promote products derived from this software without
prior written permission. For written permission, please contact
Andrew.R.Wilcox@Gmail.com.

5. Products derived from this software may not be called "AWOS"
 nor may "AWOS" appear in their name, without prior written
 permission of Andrew Wilcox.

THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESSED OR IMPLIED
WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL ANDREW WILCOX BE LIABLE FOR ANY
DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
DAMAGE.

****************************************************************/

/** \file malloc.c
 * malloc(), free() and friends.
 */

/**DEBUG turns on many error checking features.  This should be defined whenever any significant change is made to the memory allocator.**/ 
#define DEBUG					//DO NOT REMOVE THIS LINE
						//UNTIL OUT OF BETA CYCLE
						//THIS KEEPS CHECKS AND BALANCES
						//INSIDE MALLOC AND FREE

#include <kernel.h>
#include <string.h>
#include <stdlib.h>
#include <macros.h>
#include <unistd.h>

/*! \struct fullhead
 * Header of pooled memory regions.
 */
struct fullhead
{
	struct fullhead *backward;
	struct fullhead *forward;
	/** The size of the previous free buffer.  If the previous buffer is not free, this is 0. **/
	ssize_t prev;
	/** The size of this buffer.  If size is above zero, it is a free buffer.  If it below zero, it is an allocated buffer.  The size should never be zero. **/
	ssize_t size;
};
#define FULL(p) ((struct fullhead *)(p))

/** List of free buffers in kernel pool. **/
static struct fullhead kfreelist = {
	&kfreelist, &kfreelist, 0, 0
};

/** List of free buffers in user pool. **/
static struct fullhead freelist = {
	&freelist, &freelist, 0, 0
};

static long ktotal_alloc = 0;		/**amount of memory currently allocated of kernel pool**/
static long knumalloc = 0;		/**number of calls to kmalloc**/
static long knumfree = 0;		/**number of calls to kfree**/
static long ktotal_memory = 0;		/**total amount of memory in kernel pool**/

static long total_alloc = 0;		/**amount of memory currently allocated in user pool**/
static long numalloc = 0;		/**number of calls to malloc**/
static long numfree = 0;		/**number of calls to free**/
static long total_memory = 0;		/**total amount of memory in user pool**/

/** End sentinel: this is the value that is placed in a dummy block placed at the end of the pool.  It is equal to 0x80000000 on x86.**/
#define EndS	((ssize_t) (-(((1L << (sizeof(ssize_t) * 8 - 2)) - 1) * 2) - 2))

void kfree(void *);
void KiDumpFreeStruct(const char *, struct fullhead *);

/*! \fn void *kmalloc(ssize_t request);
 * \brief allocate kernel buffer
 * \param request size of new buffer, in bytes
 * \return A pointer to the new buffer, or NULL if out of memory.
 * \todo set errno to ENOMEM
 */
void *kmalloc(ssize_t request)
{
	ssize_t size = request;
	
	struct fullhead *h;
	void *buf;
	
	assert(size > 0);
	
	size += sizeof(struct fullhead);	//overhead
	
	h = kfreelist.forward;
	
	while(h != &kfreelist)
	{
		if((ssize_t)h->size >= size)
		{
			/* current buffer is big enough to allocate
			   now decide if we can split it or not */
			if((h->size - size) > (signed)(sizeof(struct fullhead)))
			{
				struct fullhead *a;
				
				a = FULL(((char *)h) + (h->size - size));	//*a = *h + size
				h->size -= size;		//decrement/split from h
				a->prev = h->size;		//previous free block = h
				a->size = -(ssize_t) size;	//negate size to mark allocated
				a->forward = h->forward;	//correct...
				a->forward->backward = a;	//...
				a->backward = h;		//...placement
				h->forward = a;			//h's forward link should point to a.
				a->forward->prev = 0;		//next buffer's previous buffer is not free.
				ktotal_alloc += size;		//add the size to total memory usage
				knumalloc++;			//# of times malloc() has been called
				KiDumpFreeStruct(__func__, a);
				buf = (void *) (((char *)a) + sizeof(struct fullhead));
				
				return buf;
			} else {
				struct fullhead *a;
				
				a = FULL(((char *)h) + h->size);		//*a = *h + size
				assert(h->backward->forward == h);		//ensure correct...
				assert(h->forward->backward == h);		//...placement
				h->backward->forward = h->forward;		//remove from freelist
				h->forward->backward = h->backward;		//remove from freelist
				ktotal_alloc += h->size;		//add the size to total memory usage
				knumalloc++;				//# of times malloc() has been called
				h->size = -(h->size);			//negate size to mark allocated
				a->prev = 0;				//next buffer not proceeded by free
				
				//buf = (void *) &(h->l);
				//buf = (void *)a;
				buf = (void *) ((char *)h + sizeof(struct fullhead));
				return buf;;
			}
		}
		h = h->forward;
	}
	
	return NULL;	//oops, no memory available
			//TODO: errno = ENOMEM;
}

/*! \fn void *malloc(ssize_t request);
 * \brief allocate user buffer
 * \param request size of new buffer, in bytes
 * \return A pointer to the new buffer, or NULL if out of memory.
 * \todo set errno to ENOMEM
 */
void *malloc(ssize_t request)
{
	ssize_t size = request;
	
	struct fullhead *h;
	void *buf;
	
	assert(size > 0);
	
	size += sizeof(struct fullhead);	//overhead
	
	h = freelist.forward;
	
	while(h != &freelist)
	{
		if((ssize_t)h->size >= size)
		{
			/* current buffer is big enough to allocate
			   now decide if we can split it or not */
			if((h->size - size) > (signed)(sizeof(struct fullhead)))
			{
				struct fullhead *a;
				
				a = FULL(((char *)h) + (h->size - size));	//*a = *h + size
				h->size -= size;		//decrement/split from h
				a->prev = h->size;		//previous free block = h
				a->size = -(ssize_t) size;	//negate size to mark allocated
				a->forward = h->forward;	//correct...
				a->backward = h;		//...placement
				h->forward = a;			//h's forward link should point to a.
				a->forward->prev = 0;		//next buffer's previous buffer is not free.
				total_alloc += size;		//add the size to total memory usage
				numalloc++;			//# of times malloc() has been called
				buf = (void *) (((char *)a) + sizeof(struct fullhead));
				
				return buf;
			} else {
				struct fullhead *a;
				
				a = FULL(((char *)h) + h->size);		//*a = *h + size
				assert(h->backward->forward == h);		//ensure correct...
				assert(h->forward->backward == h);		//...placement
				h->backward->forward = h->forward;		//remove from freelist
				h->forward->backward = h->backward;		//remove from freelist
				total_alloc += h->size;		//add the size to total memory usage
				numalloc++;			//# of times malloc() has been called
				h->size = -(h->size);		//negate size to mark allocated
				a->prev = 0;			//next buffer not proceeded by free
				
				//buf = (void *) &(h->l);
				//buf = (void *)a;
				buf = (void *) ((char *)h + sizeof(struct fullhead));
				return buf;;
			}
		}
		h = h->forward;
	}
	
	return NULL;	//oops, no memory available
			//TODO: errno = ENOMEM;
}

/*! \fn void *kcalloc(ssize_t size);
 * \brief allocate and clear kernel buffer
 * \param size size of new buffer, in bytes
 * \return A pointer to the new buffer, or NULL if out of memory.
 */
void *kcalloc(ssize_t size)
{
	char *buf = (char *)kmalloc(size);		//allocate first
	
	if(buf != NULL)					//make sure we got allocated
	{
		struct fullhead *h;
		ssize_t realsize;
		
		h = FULL(buf - sizeof(struct fullhead));//*h = *buf - overhead	
		realsize = -(h->size);			//set realsize to size in header
		realsize -= sizeof(struct fullhead);	//subtract overhead
		assert(realsize >= size);		//ensure that's the size they want
		(void)memset(buf, 0, (int)size);	//clear buffer
	}
	return (void *)buf;
}

/*! \fn void *calloc(ssize_t size);
 * \brief allocate and clear user buffer
 * \param size size of new buffer, in bytes
 * \return A pointer to the new buffer, or NULL if out of memory.
 */
void *calloc(ssize_t size)
{
	char *buf = (char *)malloc(size);		//allocate first
	
	if(buf != NULL)					//make sure we got allocated
	{
		struct fullhead *h;
		ssize_t realsize;
		
		h = FULL(buf - sizeof(struct fullhead));//*h = *buf - overhead	
		realsize = -(h->size);			//set realsize to size in header
		realsize -= sizeof(struct fullhead);	//subtract overhead
		assert(realsize >= size);		//ensure that's the size they want
		(void)memset(buf, 0, (int)size);	//clear buffer
	}
	return (void *)buf;
}

/*! \fn void *krealloc(void *old, ssize_t size);
 * \brief changes the size of an old buffer.
 * \param old pointer to old buffer
 * \param size size of new buffer, in bytes
 * \return A pointer to the new buffer, or NULL if out of memory.
 * \note If old is NULL, it will just return a new buffer as if kmalloc() had been called.
 */
void *krealloc(void *old, ssize_t size)
{
	void *new;
	ssize_t oldsize;
	struct fullhead *h;
	
	if((new = kmalloc(size)) == NULL)		//make sure we are allocated
		return NULL;
	
	if(old == NULL)					//if the old one is null, just return new
		return new;
	
	h = FULL(((char *)old) - sizeof(struct fullhead));	//*h = *old - overhead
	oldsize = -(h->size);				//get size from header
	oldsize -= sizeof(struct fullhead);			//don't count overhead in oldsize
	assert(oldsize >  0);				//make sure oldsize is above zero
	(void)memcpy((char *)new, (char *)old, (int)((size < oldsize) ? size : oldsize));
	kfree(old);
	return new;
}

/*! \fn void *realloc(void *old, ssize_t size);
 * \brief changes the size of an old buffer.
 * \param old pointer to old buffer
 * \param size size of new buffer, in bytes
 * \return A pointer to the new buffer, or NULL if out of memory.
 * \note If old is NULL, it will just return a new buffer as if malloc() had been called.
 */
void *realloc(void *old, ssize_t size)
{
	void *new;
	ssize_t oldsize;
	struct fullhead *h;
	
	if((new = malloc(size)) == NULL)		//make sure we are allocated
		return NULL;
	
	if(old == NULL)					//if the old one is null, just return new
		return new;
	
	h = FULL(((char *)old) - sizeof(struct fullhead));	//*h = *old - overhead
	oldsize = -(h->size);				//get size from header
	oldsize -= sizeof(struct fullhead);			//don't count overhead in oldsize
	assert(oldsize >  0);				//make sure oldsize is above zero
	(void)memcpy((char *)new, (char *)old, (int)((size < oldsize) ? size : oldsize));
	free(old);
	return new;
}

/*! \fn void *kfree(void *tofree);
 * \brief frees a kernel buffer
 * \param tofree pointer to buffer to deallocate
 * \return nothing
 * \note If tofree is NULL, it will return without attempting to free.
 */
void kfree(void *tofree)
{
	struct fullhead *f, *next;
		
	f = FULL(((char *)tofree) - sizeof(struct fullhead));
	KiDumpFreeStruct(__func__, f);
	knumfree++;
	
	if(tofree == NULL)
		return;
		
	if(f->size >= 0)
		next = NULL;
		
	assert(f->size < 0);
	
	assert(f->forward->prev == 0);
	ktotal_alloc += f->size;
	assert(ktotal_alloc >= 0);
	if(f->prev != 0)		//previous buffer is free
	{
		register long size = f->size;
		assert(FULL((char *)f - f->prev)->size == f->prev);
		f = FULL(((char *)f) - f->prev);
		if (size != -1) f->size -= size;
	} else {			//previous buffer is not free
		assert(kfreelist.backward->forward == &kfreelist);
		assert(kfreelist.forward->backward == &kfreelist);
		f->forward = &kfreelist;
		f->backward = kfreelist.backward;
		kfreelist.backward = f;
		f->size = -(f->size);
	}
	
	f->forward = f->forward->forward;
	next = FULL(((char *)f) + f->size);
	if(next->size > 0)
	{
		assert(FULL((char *)next + next->size)->prev == next->size);
		assert(next->backward->forward == next);
		assert(next->forward->backward == next);
		next->backward->forward = next->forward;
		next->forward->backward = next->backward;
		f->size += next->size;
		next = FULL(((char *)f) + f->size);
	}
	
	assert(next->size < 0);		//ensure next buffer really is free
	
	next->backward = f;
	next->prev = f->size;
	
	return;
}

/*! \fn void *free(void *tofree);
 * \brief frees a user buffer
 * \param tofree pointer to buffer to deallocate
 * \return nothing
 * \note If tofree is NULL, it will return without attempting to free.
 */
void free(void *tofree)
{
	struct fullhead *f, *next;
	
	f = FULL(((char *)tofree) - sizeof(struct fullhead));
	numfree++;
	if(tofree == NULL)
		return;
		
	if(f->size >= 0)
		next = NULL;
		
	assert(f->size < 0);
	
	assert(f->forward->prev == 0);
	total_alloc += f->size;
	assert(total_alloc >= 0);
	if(f->prev != 0)		//previous buffer is free
	{
		register ssize_t size = f->size;
		
		assert(FULL((char *)f - f->prev)->size == f->prev);
		f = FULL(((char *)f) - f->prev);
		f->size -= size;
	} else {			//previous buffer is not free
		assert(freelist.backward->forward == &freelist);
		assert(freelist.forward->backward == &freelist);
		f->forward = &freelist;
		f->backward = freelist.backward;
		freelist.backward = f;
		f->backward->forward = f;
		f->size = -(f->size);
	}
	
	//see if next buffer is free
	next = FULL(((char *)f) + f->size);
	if(next->size > 0)
	{
		assert(FULL((char *)next + next->size)->prev == next->size);
		assert(next->backward->forward == next);
		assert(next->forward->backward == next);
		next->backward->forward = next->forward;
		next->forward->backward = next->backward;
		f->size += next->size;
		
		next = FULL(((char *)f) + f->size);
	}
	
	assert(next->size < 0);		//ensure next buffer really is free
	
	next->prev = f->size;
	
	return;
}

/*! \fn void KiAddMemoryToKernelPool(void *buf, ssize_t len)
 * \brief adds memory to the kernel pool
 * \param buf pointer to memory to add
 * \param len size of memory to add
 * \return nothing.
 * \note appends the memory pointed to by *buf to the end of kfreelist
 */
void KiAddMemoryToKernelPool(void *buf, ssize_t len)
{
	struct fullhead *f = FULL(buf);
	struct fullhead *next;
	
	assert(len - sizeof(struct fullhead) <= ~((ssize_t)EndS + 1));	//ensure we're not overflowing
	
	f->prev = 0;
	
	//add to freelist
	assert(kfreelist.backward->forward == &kfreelist);
	assert(kfreelist.forward->backward == &kfreelist);
	f->forward = &kfreelist;
	f->backward = kfreelist.backward;
	kfreelist.backward = f;
	f->backward->forward = f;
	
	len -= sizeof(struct fullhead);		//subtract overhead
	f->size = (ssize_t)len;			//set size in header
	next = FULL(((char *)f) + len);		//*next = *f - struct head (e.g. we have room for it)
	next->prev = (ssize_t)len;		//previous (to next) is new
	next->size = EndS;			//set size to EndS - this means that this is the end
	
	ktotal_memory += len;
	
	return;
}

/*! \fn void KiAddMemoryToUserPool(void *buf, ssize_t len)
 * \brief adds memory to the user pool
 * \param buf pointer to memory to add
 * \param len size of memory to add
 * \return nothing.
 * \note appends the memory pointed to by *buf to the end of freelist
 */
void KiAddMemoryToUserPool(void *buf, ssize_t len)
{
	struct fullhead *f = FULL(buf);
	struct fullhead *next;
	
	assert(len - sizeof(struct fullhead) <= ~((ssize_t)EndS + 1));	//ensure we're not overflowing
	
	f->prev = 0;
	
	//add to freelist
	assert(freelist.backward->forward == &freelist);
	assert(freelist.forward->backward == &freelist);
	f->forward = &freelist;
	f->backward = freelist.backward;
	freelist.backward = f;
	f->backward->forward = f;
	
	len -= sizeof(struct fullhead);		//subtract overhead
	f->size = (ssize_t)len;			//set size in header
	next = FULL(((char *)f) + len);		//*next = *f - struct head (e.g. we have room for it)
	next->prev = (ssize_t)len;		//previous (to next) is new
	next->size = EndS;			//set size to EndS - this means that this is the end
	
	total_memory += len;
	
	return;
}

/*! \fn void KiGetKernelMemStats(struct KiMemStats *ms)
 * \brief get kernel pool statistics
 * \param ms pointer to where to put the stats
 * \return nothing; it is written to ms.
 */
void KiGetKernelMemStats(struct KiMemStats *ms)
{
	struct fullhead *f = kfreelist.forward;
	
	ms->NumAlloc = (ssize_t)knumalloc;
	ms->NumFree = (ssize_t)knumfree;
	ms->CurAlloc = (ssize_t)ktotal_alloc;
	ms->TotalMemory = (ssize_t)ktotal_memory;
	ms->TotalFree = 0;
	ms->MaxFreeBlk = -1;
	while(f != &kfreelist)
	{
		assert(f->size > 0);
		ms->TotalFree += (ssize_t)f->size;
		if(f->size > ms->MaxFreeBlk)
			ms->MaxFreeBlk = (ssize_t)f->size;
		f = f->forward;
	}
	
	return;
}

/*! \fn void KiGetUserMemStats(struct KiMemStats *ms)
 * \brief get user pool statistics
 * \param ms pointer to where to put the stats
 * \return nothing; it is written to ms.
 */
void KiGetUserMemStats(struct KiMemStats *ms)
{
	struct fullhead *f = freelist.forward;
	
	ms->NumAlloc = (ssize_t)numalloc;
	ms->NumFree = (ssize_t)numfree;
	ms->CurAlloc = (ssize_t)total_alloc;
	ms->TotalMemory = (ssize_t)total_memory;
	ms->TotalFree = 0;
	ms->MaxFreeBlk = -1;
	while(f != &freelist)
	{
		assert(f->size > 0);
		ms->TotalFree += (ssize_t)f->size;
		if(f->size > ms->MaxFreeBlk)
			ms->MaxFreeBlk = (ssize_t)f->size;
		f = f->forward;
	}
	
	return;
}

/*! \fn void KiGetNumAlloc(BOOL user)
 * \brief get number of allocations made
 * \param user whether to get number of user pool allocations or kernel pool allocations
 * \return number of allocations.
 */
int KiGetNumAlloc(BOOL user)
{
	if(user == TRUE)
		return numalloc;
	else
		return knumalloc;
}

/*! \fn void KiDumpPool(void *buf)
 * \brief dumps pool starting at *buf
 * \param buf pointer of memory to start dumping at
 * \return nothing.
 */
void KiDumpPool(void *buf)
{
	struct fullhead *f = FULL(buf);
	
	while(f->size != EndS)
	{
		ssize_t size = f->size;
		
		if(size < 0)
		{
			size = -size;
			printf("Allocated buffer: size %6ld bytes.\n", (long)size);
		} else {
			char *err = "";
			
			assert(size > 0);
			if((f->backward->forward != f) || (f->forward->backward != f))
				err = "  (Bad free list links)";
			printf("Free block:       size %6ld bytes.%s\n", (long)size, err);
		}
		f = FULL(((char *)f) + size);
	}
}

/*! \fn void KiDumpFreeStruct(const char *func, struct fullhead *fh)
 * \brief dumps contents of a fullhead
 * \param func function name
 * \param fh pointer to header to dump
 * \return nothing.
 * \note if #DEBUG is not enabled, KiDumpFreeStruct will return without printing anything.
 */
void KiDumpFreeStruct(const char *func, struct fullhead *fh)
{
#ifdef DEBUG
	dprintf("%s:prev=%08lX  size=%03li  back=%8p  cur=%8p  forward=%8p\n", func,\
	fh->prev, fh->size, fh->backward, fh, fh->forward);
#endif
	return;
}
